package com.xufx.algorithm.sort;

/**
 * 快速排序
 * 步骤:
 * 1. 选取基准值
 * 2. 形成这种形式--> [比基准值小的值]基准值[比基准值大的值]
 * 3. 重复1，2的过程
 * 4. 组合上面的过程
 * 特别注意：下面的代码块1和代码块2的位置一定不能出错。
 * 如果反过来，结果就不对；
 * 原因：pivot里面存的是左边的值
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] nums = new int[]{0,-1,2,3};
        quickSort(nums, 0, nums.length - 1);
        for (int num: nums) {
            System.out.println(num);
        }
    }

    private static void quickSort(int[] nums, int leftBound, int rightBound) {
        if(leftBound >= rightBound){
            return;
        }
        int mid = patition(nums, leftBound, rightBound);
        quickSort(nums, leftBound, mid - 1);
        quickSort(nums, mid + 1, rightBound);
    }

    private static int patition(int[] nums, int l, int r) {
        int pivot = nums[l];
        while(l < r){
            // 代码块1
            while(l < r && nums[r] >= pivot){
                r--;
            }
            if(l < r){
                nums[l] = nums[r];
                l++;
            }
            // 代码块2
            while(l < r && nums[l] <= pivot){
                l++;
            }
            if(l < r){
                nums[r] = nums[l];
                r--;
            }

        }
        nums[l] = pivot;
        return l;
    }
}
